1. Field of the Invention
The invention relates generally to the reclamation of storage during execution of a process and more specifically to incremental garbage collectors.
2. Description of the Prior Art
Popular programming languages such as C or C++ permit programmers to explicitly allocation and free portions of memory during execution of the program. While the ability to allocate and free memory greatly simplifies many programming tasks, it does present one difficulty: the programmer must carefully coordinate allocating and freeing memory. Once the memory has been allocated, it must not be freed until the program is in fact done using it; once the program is in fact finished using the memory, it must be freed, otherwise, it will remain unavailable for reuse by the program or by other programs.
The difficulty of avoiding errors in freeing data increases as the size of a program grows. Memory is often allocated in one module of the program, used in other modules of the program, and freed in still other modules. These modules are often written by different programmers and are executed in different orders. The difficulty also increases as a program ages. Most programs are modified to fix bugs or add new features, and the people who do the modifications are generally different from those who write the original program. The manner in which the modified program employs blocks of memory or allocates or frees them may be different from that contemplated by the original authors of the program.
The consequences of mistakes in freeing allocated memory have further become more serious as more and more programs "run forever", that is, they are continually executed in computers that are never shut down. A program which does not free all of the memory it allocates will appear to operate correctly when executed intermittently; however, when it runs forever, it will run out of memory and fail. Such failures are particularly problematical, first, because the very fact that the program runs forever means that other programs are relying on it. When it fails, they often cannot continue. Second, when such failures happen depends on the total condition of the system in which the program is executing; that makes the failures difficult to anticipate, difficult to understand and correct, and difficult to recover from. Finally, even before a program that is not freeing memory correctly fails, the memory resources it fails to free remain unavailable for use by other programs, and consequently, the entire computer system operates less efficiently than it would otherwise.
One way of solving the problems posed by programs which free their own memory is to reserve all freeing of memory to a special program called a garbage collector, so called because it collects garbage memory, that is, blocks of memory that are no longer being used by a program, and reclaims them for later reuse. FIG. 1 shows how the memory 101 used by a computer program when it is being executed looks to a garbage collector. The program executes on an entity called a process. Each process has its own process address space 103 and the program executing on the process can only reference data in the process's address space 103. For purposes of the present discussion, process address space 103 is subdivided into two parts: committed address space 131, which is that part of process address space 103 which has been mapped to the physical devices that make up the memory in the computer system that the process is executing on, and uncommitted address space 132, which has not been so mapped. Before a program can actually read data from or write data to a location in process address space 103, that location must be part of committed address space 131.
Committed address space 131 further includes automatically-allocated memory 107, heap 109, and free memory 114. Not shown here, but also contained in committed address space 131 is the code executed by the program. Automatically-allocated memory 107 is memory that the program automatically allocates as it initializes itself and executes calls and returns from procedures. The automatically allocated storage is shown at 107. It typically includes data 121 that is in the computer's hardware registers when the program's process is actually running on the computer, static data 123, that is, data that remains available for the entire execution of the program, and stack 125, which has a frame 127 for each procedure that the program has called and not yet returned from, with the frame for the most recently-called procedure being at the top of the stack. Just as the program automatically allocates storage 107, it automatically deallocates it; when the program returns from a call to a procedure, the frame for the procedure is removed from the stack; similarly, the storage for the static data and the hardware registers is automatically deallocated when the program ceases execution.
When an allocation function in a program allocates storage, the allocated storage makes up an area called the heap 109, because the storage in this area is not ordered like the data in the stack. Storage in the heap comes from free memory 114. When a portion 104 of free memory 114 is allocated, the allocation function returns a pointer 108 to the portion 104 that was allocated to the program which executed the allocation function. The pointer is simply a data item which contains the location in the memory system of the portion 104. The program stores the pointer to the newly-allocated portion in previously-allocated memory, either in the automatically allocated memory 107 or in heap 109. The program can only use the newly-allocated portion 104 as long as it has a pointer to it. When the program no longer has a pointer to the portion 104, the portion 104 has become garbage, as shown at 111. The allocation function allocates portions 104 from free memory 114. Whenever a program is done with a portion 104, it should return it to free memory 114.
Efficient use of the physical memory resources of the computer system that the process to which process address space 103 is executing on requires that committed address space 131 not be too much larger than the actual current physical memory requirements of the process.
For this reason, allocation and freeing of memory should be accompanied by adjustments in the size of committed address space 131. The component of the computer system that handles automatic allocation and deallocation and allocation and freeing by means of allocation and free functions and manages committed address space 131 is termed herein the allocator. Once the allocator has decommitted a portion of committed address space 131, that is, terminated the mapping between that portion of process address space 103 and a portion of physical memory, any reference by a program being executed by the process to which address space 103 belongs to the decommitted portion of its address space will result in a segmentation or protection fault. In the case of free address space 114, commitment and decommitment are done by mapping free blocks 113 into free memory 114 and unmapping free blocks 113 from free memory 114. To manage free blocks 113, the allocator uses free list 129.
As would be expected from FIG. 1, garbage collectors work by detecting memory portions 104 that no longer have pointers 108 pointing to them and returning such "garbage" portions 111 to free memory 114. There are a number of different techniques for doing garbage collection; the paper by Paul R. Wilson, "Uniprocessor Garbage Collection Techniques", in 1992 International Workshop on Memory Management (St. Malo, France, September, 1992), published in the Springer-Verlag Lecture Notes in Computer Science series, provides an overview. One popular technique is termed mark-sweep collection. In mark-sweep collection, the garbage collector starts at a root consisting of all of the storage for the execution of the program that was not allocated by the allocation function (typically, the hardware registers and automatically-allocated memory 107 in FIG. 1) and follows the pointers 108 to portions 104. Whenever it finds a new portion 104, it marks the portion as being in use by the execution of the program to which automatically-allocated storage 107 belongs. The marking may be done in the portion 104 itself or in a table which keeps track of the status of the portions 104. Then it looks for pointers 108 in the newly-marked portion and follows each pointer that points to a previously-unmarked portion. That portion is then marked and examined as just described. Once all of the portions 104 that are reachable from automatically-allocated storage 107 have been marked, the garbage collector scans process address space 103 to determine which portions 104 have not been marked. Those that are not marked are garbage and the garbage collector returns them to free memory 114.
The simplest way to do garbage collection is by halting the process that automatically allocated storage 107 belongs to, doing all of the marking, scanning, and returning of portions at once, and then restarting the process. The disadvantage with this approach is that the process is not available to other processes while the garbage collection is going on. To solve this problem, incremental garbage collectors have been developed in which the marking operation is done in increments, with the increments being interleaved with the execution of the program. Once the marking has been done in this fashion, the scanning and collection operations are done, so that there are only short interruptions in the execution of the process. One set of marking, scanning, and collection operations is termed a garbage collection cycle.
An incremental garbage collector must be able to cope with the problem that the memory portions used by the program being executed change behind the garbage collector's back, that is, that the program has not stopped executing, and consequently may either change the value of a pointer in a portion that has already been marked or invoke a free function and thereby cause a portion to be decommitted that has been marked but whose pointers have not yet been followed. If the value of a pointer is changed to point to a portion that previously had no pointer to it, the garbage collector will not scan the portion and may erroneously treat the portion as garbage and return it to free memory 114; at the same time, the portion previously pointed to by the pointer has been marked and will not be returned to free memory 114. The same will be true of other portions pointed to only by pointers in that portion. The first error is more serious than the second, since in the second case, the next garbage collection cycle will detect that the portion that has been erroneously marked is garbage and will return it to free memory 114. If a portion has been decommitted, an attempt by the garbage collector to follow a pointer to the portion will result in a segmentation or protection fault.
To deal with the fact that pointers in the memory portions can change behind the garbage collector's back, the designers of incremental garbage collectors employ read barriers or write barriers to detect changes in the values of pointers and to keep track of those changes which will affect garbage collection. The new pointers are then followed and the portions they point to are marked if they have not been. For a discussion of read and write barriers, see page 18 of the Wilson reference supra.
Dealing with portions that are decommitted because a program has invoked a free function is more difficult. Currently, three solutions are known:
Prohibiting the use of explicit deallocation by programs for which the garbage collector is collecting garbage; languages such as Java or Small Talk that include provisions for automatic garbage collection take this approach. PA1 Not decommitting memory at all until a process terminates. This is the approach generally used in operating systems of the UNIX.RTM. type. PA1 Decommitting memory portions only once during a garbage collection cycle. This is done by copying garbage collectors and snapshot garbage collectors such as the one implemented by Gustavo Rodriguez-Rivera and Vince Russo at Purdue University.
All three solutions have disadvantages. The disadvantage of the first solution is that prohibiting the use of explicit deallocation prevents garbage collectors from being used with two important classes of programs: those where considerations of time or space efficiency require that the programmer specify the allocation and free operations and more importantly, legacy programs which were not written for garbage collectors. Legacy programs are old programs which still work and can be upgraded or reimplemented only at great expense. The programs thus typically end up being executed in environments which have little or no resemblance to the environments they were written for. The fail-safe use and maintenance of such "legacy" programs is one of the most pressing problems of computer science, and because many incremental garbage collectors do not operate properly with legacy programs, they cannot be used to help solve the legacy program problem. The disadvantage with the second solution is that the process keeps the largest amount of memory committed to it during its execution until it terminates. Where there are large variations in the amount of memory required by a process during execution, this results in inefficient use of memory resources.
There are three disadvantages with the third solution. One disadvantage is that memory can be decommitted only once in a garbage collection cycle. That in turn requires the allocator to maintain a larger committed address space 131 than would be necessary if it could decommit memory more frequently, resulting in a less efficient use of the computer system's physical memory resources. Another is that memory is not available to another process until the next garbage collection cycle. The third is that restricting the decommitting of memory to once a cycle increases the length of time required for that part of the cycle and thereby conflicts with an important design goal of incremental garbage collectors, namely designing the cycle such that each stage of it is either short or may be subdivided into a sequence of short operations. These disadvantages increase as the length of the garbage collection cycle increases. Where garbage collection is used as a backup memory recovery mechanism with programs that allocate and free memory using the allocation and free functions, a single cycle may last for many hours.
What is needed is an incremental garbage collector which permits decommittal of memory by the allocator and consequently can be used with programs that explicitly free storage but has a garbage collection cycle that is as efficient as those of garbage collectors that cannot be used with such programs. It is an object of the invention to provide such an incremental garbage collector.